/**
 * 
 */
package leetCode;

import java.util.TreeMap;

/**
 * @author zhong
 *
 */
public class MyCalendarII {
	class Node {
		public Node(int start, int end) {
			l = start;
			r = end;
			count = 1;
		}

		int count = 0;
		int l, r;
		Node left, right;
	}

	Node root = null;
	TreeMap<Integer, Integer> calendar = new TreeMap<>();

	/**
	 * 用TreeMap的方法
	 * 
	 * @param start
	 * @param end
	 * @return
	 */
	public boolean book2(int start, int end) {
		Integer floorKey = calendar.floorKey(start);
		if (floorKey != null && calendar.get(floorKey) > start)
			return false;
		Integer ceilingKey = calendar.ceilingKey(start);
		if (ceilingKey != null && ceilingKey < end)
			return false;

		calendar.put(start, end);
		return true;
	}

	public boolean book(int start, int end) {
		if (root == null) {
			root = new Node(start, end);
			return true;
		} else {
			return insert(root, null, false, start, end);
		}
	}

	private boolean insert(Node cur, Node parent, boolean leftInsert, int start, int end) {
		boolean success = true;
		if (cur == null) {
			cur = new Node(start, end);
			if (leftInsert) {
				parent.left = cur;
			} else {
				parent.right = cur;
			}
			return true;
		}
		if (end <= cur.l) {
			return insert(cur.left, cur, true, start, end);
		} else if (start >= cur.r) {
			return insert(cur.right, cur, false, start, end);
		} else {// 有重叠
			if (cur.count == 2) {// 如果已经有两个重叠，则不能继续重叠了
				return false;
			}
			if (start <= cur.l && end >= cur.r) {// se包lr， 完全覆盖,slre
				if (start != cur.l) {
					success &= insert(cur.left, cur, true, start, cur.l);
				}
				if (success && end != cur.r) {
					success &= insert(cur.right, cur, false, cur.r, end);
				}
				if (success && cur.count == 1) {// l，r的count++
					cur.count = 2;
					return true;
				} else {
					return false;
				}
			} else if (cur.l <= start && cur.r >= end) {// lr包se，lser,可以l==s,e==r
				if (cur.count == 1) {
					cur.count = 2;
					if (cur.l != start) {
						Node lNode = new Node(cur.l, start);
						lNode.left = cur.left;
						cur.left = lNode;
						// lNode.count = 2;
					}
					if (cur.r != end) {
						Node rNode = new Node(end, cur.r);
						rNode.right = cur.right;
						cur.right = rNode;
						// rNode.count = 2;
					}
					cur.l = start;
					cur.r = end;
					return true;
				} else {
					return false;
				}
			} else if (start <= cur.l && end <= cur.r) {// sler
				if (cur.l != start) {
					success &= insert(cur.left, cur, true, start, cur.l);
				}
				if (success && cur.count == 1) {
					cur.count = 2;
					if (end != cur.r) {
						Node rNode = new Node(end, cur.r);
						// rNode.count = 2;
						rNode.right = cur.right;
						cur.right = rNode;

						cur.r = end;
					}
					return true;
				} else {
					return false;
				}
			} else { // lsre
				if (cur.r != end) {
					success &= insert(cur.right, cur, false, cur.r, end);
				}
				if (success && cur.count == 1) {
					cur.count = 2;
					if (cur.l != start) {
						Node lNode = new Node(cur.l, start);
						cur.l = start;
						lNode.left = cur.left;
						cur.left = lNode;
						// lNode.count = 2;
					}
					return true;
				} else {
					return false;
				}
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyCalendarII MyCalendar = new MyCalendarII();
		System.out.println(MyCalendar.book(24, 40)); // t
		System.out.println(MyCalendar.book(43, 50));// t
		System.out.println(MyCalendar.book(27, 43));// t
		System.out.println(MyCalendar.book(5, 21));// t
		System.out.println(MyCalendar.book(30, 40));// f
		System.out.println(MyCalendar.book(14, 29));// f
		System.out.println(MyCalendar.book(3, 19));// t
		System.out.println(MyCalendar.book(3, 14));// f
		System.out.println(MyCalendar.book(25, 39));// f
		System.out.println(MyCalendar.book(6, 19));// f
		// ["MyCalendarTwo","book","book","book","book","book","book","book","book","book","book"]
		// [[],[24,40],[43,50],[27,43],[5,21],[30,40],[14,29],[3,19],[3,14],[25,39],[6,19]]
	}

}
